package alg20241102;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Text2 {
    public static void main(String[] args) {
        String ss = "abcabcabcabc";
        char[] s = ss.toCharArray();
        Map<String, Integer> hash = new HashMap<>();

        for (int left = 0, right = 0; right < s.length; right+=3) {
            StringBuffer sb = new StringBuffer();
            int k = 0;
            while(k > 3){
                sb.append(s[right+k]);
                k++;
            }
            hash.getOrDefault(sb,1);

        }

    }
    //没写对。。。。
    public List<Integer> findSubstring1(String ss, String[] words) {
        List<Integer> ret = new ArrayList<>();
        int len1 = words.length;
        HashMap<String, Integer> hash1 = new HashMap<>();
        HashMap<String, Integer> hash2 = new HashMap<>();
        for(String word : words){
            hash2.put(word, hash2.getOrDefault(word, 0) + 1);
        }
        char[] s = ss.toCharArray();
        int len2 = words[0].length();  //一个单词的长度
        int count = 0; //计数器
        for (int i = 0; i < len2; i++) {
            for (int left = i, right = i; right < s.length; right+=len2) {
                int count1 = len2;    //记录单词的长度 遍历字符数组count1次将字符组成字符串
                StringBuffer sb = new StringBuffer();
                while(count1 > 0){
                    sb.append(s[right + count1 - len2]);
                    count1--;
                }
                //将字符串放入hash1  即进窗口
                String str = sb.toString();
                hash1.put(str, hash1.getOrDefault(str, 0) + 1);
                //判断是不是有效字符串
                if(hash1.get(str) <= hash2.get(str)) count++;
                //判断出窗口
                while(right - left + 1 > len1){
                    //判断是不是有效字符串
                    int count3 = len2;    //记录单词的长度 遍历字符数组count1次将字符组成字符串
                    StringBuffer sb1 = new StringBuffer();
                    while(count3 > 0){
                        sb.append(s[left + count3 - len2]);
                        count3--;
                    }
                    String str1 = sb1.toString();
                    if(hash1.get(str1) <= hash2.get(str1)) count--;
                    //出窗口
                    hash1.put(str1, hash1.get(str1)-1);
                    if(hash1.get(str1) == 0){
                        hash1.remove(str1);
                    }
                }
                //更新结果
                if(count == len1) ret.add(left);

            }
        }

        return ret;
    }
   //标准答案
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        Map<String, Integer> hash1 = new HashMap<>(); //保存单词出现的频次
        for(String word : words){
            hash1.put(word, hash1.getOrDefault(word, 0) + 1);
        }
        int len = words[0].length(), m = words.length;
        for (int i = 0; i < len; i++) {      //执行的次数
            Map<String, Integer> hash2 = new HashMap<>();
            for(int left = i, right = i, count = 0; right + len <= s.length(); right += len){
                //进窗口  + 维护count
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                if(hash2.get(in) <= hash1.getOrDefault(in, 0)) count++;
                //判断   出窗口
                if(right - left + 1 > len * m) {
                    String out = s.substring(left, left + len);
                    //维护count
                    if(hash2.get(out) <= hash1.getOrDefault(out, 0)){
                        count--;
                    }
                    //出窗口
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                //更新结果
                if(count == m) ret.add(left);
            }
        }
        return ret;
    }

}
